from collections import defaultdict


class Solution(object):
    # 在滑动窗口类型的问题中都会有两个指针，一个用于「延伸」现有窗口的 rr 指针，
    # 和一个用于「收缩」窗口的 ll 指针。在任意时刻，只有一个指针运动，而另一个
    # 保持静止。我们在 ss 上滑动窗口，通过移动 rr 指针不断扩张窗口。当窗口包含
    # tt 全部所需的字符后，如果能收缩，我们就收缩窗口直到得到最小窗口。

    # 作者：LeetCode-Solution
    # 链接：https://leetcode.cn/problems/minimum-window-substring/solution/zui-xiao-fu-gai-zi-chuan-by-leetcode-solution/
    # 来源：力扣（LeetCode）
    # 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    def minWindow(self, s: str, t: str) -> str:  # O(n)
        need = defaultdict(int)
        for c in t:
            need[c] += 1

        needCnt = len(t)
        i = 0
        res = (0, float('inf'))  # initialize window (0, inf)
        for j, c in enumerate(s):
            if need[c] > 0:
                needCnt -= 1
            need[c] -= 1

            if needCnt == 0:  # all elts in t are included
                while True:
                    c = s[i]
                    if need[c] == 0:  # encounter a needed element
                        break         # stop moving i
                    need[c] += 1
                    i += 1

                # record new window (i, j)
                if j - i < res[1] - res[0]:
                    res = (i, j)
                
                # increment the position i
                need[s[i]] += 1
                needCnt += 1
                i += 1

        return '' if res[1] > len(s) else s[res[0]:res[1]+1]


if __name__ == "__main__":
    soln = Solution()
    assert soln.minWindow("ADOBECODEBANC", "ABC") == "BANC"
